|
Discrete tomography〔 Herman, G. T. and Kuba, A., Discrete Tomography: Foundations, Algorithms, and Applications, Birkhäuser Boston, 1999 〕〔 Herman, G. T. and Kuba, A., Advances in Discrete Tomography and Its Applications, Birkhäuser Boston, 2007 〕 focuses on the problem of reconstruction of binary images (or finite subsets of the integer lattice) from a small number of their projections. In general, tomography deals with the problem of determining shape and dimensional information of an object from a set of projections. From the mathematical point of view, the object corresponds to a function and the problem posed is to reconstruct this function from its integrals or sums over subsets of its domain. In general, the tomographic inversion problem may be continuous or discrete. In continuous tomography both the domain and the range of the function are continuous and line integrals are used. In discrete tomography the domain of the function may be either discrete or continuous, and the range of the function is a finite set of real, usually nonnegative numbers. In continuous tomography when a large number of projections is available, accurate reconstructions can be made by many different algorithms. It is typical for discrete tomography that only a few projections (line sums) are used. In this case, conventional techniques all fail. A special case of discrete tomography deals with the problem of the reconstruction of a binary image from a small number of projections. The name ''discrete tomography'' is due to Larry Shepp, who organized the first meeting devoted to this topic (DIMACS Mini-Symposium on Discrete Tomography, September 19, 1994, Rutgers University). ==Theory== Discrete tomography has strong connections with other mathematical fields, such as number theory,〔R.J. Gardner, P. Gritzmann, Discrete tomography: determination of finite sets by X-rays, Trans. Amer. Math. Soc. 349 (1997), no. 6, 2271-2295.〕〔L. Hajdu, R. Tijdeman, Algebraic aspects of discrete tomography, J. reine angew. Math. 534 (2001), 119-128.〕〔A. Alpers, R. Tijdeman, The Two-Dimensional Prouhet-Tarry-Escott Problem, Journal of Number Theory, 123 (2), pp. 403-412, 2007 ().〕 discrete mathematics,〔S. Brunetti, A. Del Lungo, P. Gritzmann, S. de Vries, On the reconstruction of binary and permutation matrices under (binary) tomographic constraints. Theoret. Comput. Sci. 406 (2008), no. 1-2, 63-71.〕〔A. Alpers, P. Gritzmann, On Stability, Error Correction, and Noise Compensation in Discrete Tomography, SIAM Journal on Discrete Mathematics 20 (1), pp. 227-239, 2006 ()〕〔P. Gritzmann, B. Langfeld, On the index of Siegel grids and its application to the tomography of quasicrystals. European J. Combin. 29 (2008), no. 8, 1894-1909.〕 complexity theory〔R.J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of reconstructing lattice sets from their X-rays. Discrete Math. 202 (1999), no. 1-3, 45-71.〕〔C. Dürr, F. Guiñez, M. Matamala, Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard. ESA 2009: 776-787.〕 and combinatorics.〔H.J. Ryser, Matrices of zeros and ones, Bull. Amer. Math. Soc. 66 1960 442-464.〕〔D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (1957), 1073-1082.〕〔E. Barcucci, S. Brunetti, A. Del Lungo, M. Nivat, Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays, Discrete Mathematics 241(1-3): 65-78 (2001).〕 In fact, a number of discrete tomography problems were first discussed as combinatorial problems. In 1957, H. J. Ryser found a necessary and sufficient condition for a pair of vectors being the two orthogonal projections of a discrete set. In the proof of his theorem, Ryser also described a reconstruction algorithm, the very first reconstruction algorithm for a general discrete set from two orthogonal projections. In the same year, David Gale found the same consistency conditions, but in connection with the network flow problem. Another result of Ryser's is the definition of the switching operation by which discrete sets having the same projections can be transformed into each other. The problem of reconstructing a binary image from a small number of projections generally leads to a large number of solutions. It is desirable to limit the class of possible solutions to only those that are typical of the class of the images which contains the image being reconstructed by using a priori information, such as convexity or connectedness. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「discrete tomography」の詳細全文を読む スポンサード リンク
|